package com.topInterview;

import java.util.Stack;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/20 18:29
 */
public class Leecode84_largestRectangle {

    public static int largestRectangleArea(int[] heights) {
        int max = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                int j = stack.pop();
                //左边比j小的数stack.peek()，右边比j小的为heights[i]
                int k = stack.isEmpty() ? -1 : stack.peek();
                //结算j位置的最大面积
                int cur = (i - k - 1) * heights[j];
                max = Math.max(max, cur);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int cur = (heights.length - k - 1) * heights[j];
            max = Math.max(max, cur);
        }
        return max;


    }

    public static void main(String[] args) {
        int[] r = {2,4};
        largestRectangleArea(r);
    }
}
